package com.bing.java.queue;

import java.util.Iterator;

/**
 * 队列实现
 * 
 * @author bing
 *
 *         2019年11月9日 下午3:38:27
 * 
 *         链表实现方式
 *         
 *         下面是队列的链表实现，需要维护 first 和 last 节点指针，分别指向队首和队尾。
这里需要考虑 first 和 last 指针哪个作为链表的开头。因为出队列操作需要让队首元素的下一个元素成为队首，所以需要容易获取下一个元素，
而链表的头部节点的 next 指针指向下一个元素，因此可以让 first 指针链表的开头。
 */
public class ListQueue<Item> implements MyQueue<Item> {

	private int N = 0;

	private Node first;    //第一个元素
	private Node last;     //最后一个元素

	private class Node {
		Item item;
		Node next;
	}

	@Override
	public MyQueue<Item> add(Item item) {
		Node newNode = new Node();     
		newNode.item = item;   //当前节点得值为该元素
		newNode.next = null;   //上一个节点为Null

		if (isEmpty()) {       //空得话第一个元素是它，最后一个元素也是它
			first = newNode;
			last = newNode;
		} else {
			last.next = newNode;   //不是空，代表有元素 那下一个元素就是自己，并且最后元素也是自己
			last = newNode;
		}
		N++;
		return this;
	}

	@Override
	public Item remove() throws Exception {
		if (isEmpty()) {
			throw new Exception("queue is empty");
		}

		Node node = first;    //取出第一个元素
		first = first.next;   //第一个元素变成了下一个元素
		N--;

		if (isEmpty()) {
			last = null;
		}

		return node.item;
	}

	@Override
	public int size() {
		return N;
	}

	@Override
	public boolean isEmpty() {
		return N == 0;
	}

	@Override
	public Iterator<Item> iterator() {
		return new Iterator<Item>() {

			Node cur = first;

			@Override
			public boolean hasNext() {
				return cur != null;
			}

			@Override
			public Item next() {
				Item item = cur.item;
				cur = cur.next;
				return item;
			}
		};
	}
	
	public static void main(String[] args) throws Exception {
		ListQueue<Integer> listQueue = new ListQueue<Integer>();
		listQueue.add(8);
		listQueue.add(9);
		System.out.println(listQueue.remove());
	}
}
